The present invention relates to electronic signature techniques and more particularly to group signature techniques.
The fundamental object enabling the public part of a cryptographic key (public key) to be trusted is the certificate. The certificate standard used in numerous networks, including the Internet, is X.509, version 3. A specification thereof is provided by the PKIX working group of the IETF (“Internet Engineering Task Force”) in the Request For Comments (RFC) 3280, “Internet X.509 Public Key Infrastructure; Certificate and Certificate Revocation List (CRL) Profile” published in April 2002. The certificate is an object comprising in particular:                the public key to be certified;        the identity of its possessor;        a period of validity;        a cryptographic signature of these data by the private key of a Certifying Authority (CA) that issued the certificate.        
Trusting the public key associated with an identity amounts to making sure of the validity of the certificate. For PKIX, a certificate is valid at a given instant T (in terms of trust):                either if it is explicitly declared as “trusted certificate”. In practice, the certificates of users are never declared trusted. Rather, a reduced number of trusted certificates is declared, consisting of the certificates of certain CAs;        or if it satisfies the following conditions:                    the cryptographic signature of the certificate is mathematically valid;            the instant T forms part of the period of validity of the certificate;            the certificate is not revoked at the instant T;            the public key of the issuing CA is available through a certificate of the CA, and this certificate of the CA is itself valid at the instant T.                        
The electronic signature function makes it possible to guarantee the authenticity of a document, i.e. to dependably authenticate its signatory or signatories and to guarantee that the document has not been modified (integrity). The electronic signature is often used to guarantee nonrepudiation. The nonrepudiation of a document consists in guarding against a subsequent denial from its author.
This traditional electronic signature transposes the mechanism of manual signing over to the electronic world. Another form of electronic signature, relying on multiplayer cryptography techniques, offers features which both comparable to regular signing (some guarantee of the origin of a message) and radically different (anonymity of the signatory among a group of people). The group signature allows an individual member of a group administered by an authority to effect a signature in the name of the group.
The group signature involves at least one signatory, a group of individuals to which the signatory belongs, and an authority. It allows an individual to sign in the name of a group of individuals, but anonymously. When an entity verifies a group signature, it is certain that the signature has indeed been effected by a member of the group, without being able to determine which one only one entity can determine the identity of the signatory: the authority. In this case, it is said to “open” the signature. The group signature is then said to have “limited anonymity”. This possibility of withdrawing the anonymity may turn out to be useful, in particular in case of fraud or to ensure the proper operation of a service such as for example an auction service. In general, the group signature requires an initialization phase and involves specific cryptographic keys.
The group signature mechanisms are not standardized. Examples thereof are described in the articles:                D. Chaum, et al., “Group signatures”, Eurocrypt'91. 1991;        G. Atienese, et al., “A Practical and Provably Secure Coalition-Resistant Group Signature Scheme”, Crypto 2000, http://www.zurich.ibm.com/se curity/publications/2000/CAJT2000.pdf.        
These known group signature techniques generally make it possible to withdraw anonymity. However, they have drawbacks: they are unwieldy to set up, require an administrating authority, and their keys are incompatible with the market standards. The management of the groups greatly complicates these group signature mechanisms. In general, it is the authority that is charged with this. However, this does not detract from the complexity of the operations for enrolling a new member into an already existing group and of removing a member from a group. As the signing operations call upon nonstandard keys, a user furnished with an RSA key and with an X.509 certificate will not be able to use this key to effect his group signature.
The “ring-signature” is a multiplayer cryptography signature algorithm which is not properly speaking a group signature. It differs from the group signature in that:                the people in whose names the signatory produces his ring-signature are not part of a formalized group and have not therefore given explicit consent;        there is no authority;        unless the signatory is explicitly mentioned, anonymity cannot be withdrawn.        
However, it is necessary that all possible signatories should have a public key accessible to the signatory. There is no need for a prior phase of configuration. As there is no authority, the ring-signature offers complete anonymity, i.e. nobody can determine who is the actual signatory, unless complementary mechanisms are introduced.
This ring-signature mechanism was first introduced by R. L. Rivest, et al.: “How to Leak a Secret”, Asiacrypt'01, December 2001, http://theory.lcs.mit.edu/-rivest/RivestSh amirTauman-HowToLeakASecret.pdf). Variants thereof have since been proposed, for example by E. Bresson, et al, “Threshold Ring Signatures and Applications to Ad-hoc Groups” Crypto'02, August 2002.
The ring-signature involves a signatory Es from among a set E of r entities or individuals Ei able to sign (i ranging from 1 to r), furnished with respective public keys PUBi accessible to the signatory. Each of the public keys PUBi is associated, in an asymmetric cryptography scheme such as for example the RSA, with a private key PRi known only to the member Ei. The signatory Es belongs to the set E (1≦s≦r). A ring-signature algorithm allows Es to sign in the name of E but anonymously in the sense that an entity verifying a ring-signature is certain that the signature was indeed effected by a member of E, without being able to determine which one.
Let M denote the set of messages or documents able to be signed. The number b designating a “ring width” expressed in bits, B denotes the set of messages of b bits. A “combination” C determines a combination function Cm,v as a function of any number of input variables in B, taking its values in B, dependent on at least two parameters m ∈ M and v ∈ B and such that, all the input variables except any one being fixed, Cm,v is a bijection of B into B. To minimize the algorithmic complexity, it is advisable that (i) for all values of the input variables, Cm,v be easy to calculate, and (ii) the inverse of each of the aforesaid bijections be also easy to calculate. This inverse operation is called “solving of the ring equation”. For certain variables y1, y2, . . . , yr, “the ring equation” is expressed in the following manner:Cm,v (y1, y2, . . . yr)=v  (1)
Moreover we define a function A which, with asymmetric cryptography keys (PUB, PR), where PUB is a public key and PR a corresponding private key, associates a pair (g, h) such that:                g is a function with values in B which can depend on PUB but not on PR;        h is a function of a variable of B which can depend on PUB and PR;        g and h are inverses of one another, i.e.:                    g(h(y))=y for any y in B; and            h(g(x))=x for any x acceptable as an input of g.                        
The definition of the triplet (b, C, A) characterizes a ring-signature scheme. A “ring-signature production system” is defined by such a triplet (b, C, A) , a set of entities E={Ei/1≦i≦r} each having a pair of public and private keys PUBi, PRi defining a pair of functions (gi, hi)=A(PUBi, PRi), an index s ∈ {1,2, . . . r} designating a signatory entity Es, and a message m ∈ M.
This ring-signature production system being fixed, the provision of the public keys PUBi of the r entities Ei, of an element v of B, and of r elements xi (1≦i≦r) is called the ring-signature of the message m in the name of E. This signature is valid if it satisfies the ring equation (1) for the r input variables yi=gi(xi) of B (1≦i≦r).
An algorithm for ring-signature production by S thus executes as follows:                /a/ randomly choose v in B;        /b/ choose random elements xi for all the i≠s;        /c/ solve the ring equation in ys by fixing the input variables yi=gi(xi) for i≠s by means of the public keys PUBi, i.e. determine ys such thatCm,v(g1(x1), . . . , gs−1(xs−1), ys, gs+1(xs+1), . . . , gr(xr))=v        /d/ calculate Xs=hs(ys) by means of the private key PRs; and        /e/ deliver the ring-signature: (PUB1, PUB2, . . . , PUBr;v;x1, x2, . . . , xr).        
This ring-signature is then verifiable by the following verification algorithm:                /f/ calculate the yi=gi(xi) for 1≦i≦r by means of the public keys PUBi;        /g/ evaluate the combination function Cm,v(y1, y2, . . . , yr); and        /h/ accept the ring-signature if and only if the result is v.        
The ring-signature makes it possible to remedy the drawbacks of the conventional group signature procedures. However, in its known versions, it precludes the ability to withdraw anonymity. Now, the ability to withdraw anonymity is an essential property for a certain number of applications such as for example electronic suggestion boxes, electronic lottery applications, electronic auction services, etc.
An object of the present invention is to adapt the ring-signature technique to allow the withdrawal of anonymity.